|
In computational number theory, Williams' ''p'' + 1 algorithm is an integer factorization algorithm, one of the family of algebraic-group factorisation algorithms. It was invented by Hugh C. Williams in 1982. It works well if the number ''N'' to be factored contains one or more prime factors ''p'' such that ''p'' + 1 is smooth, i.e. ''p'' + 1 contains only small factors. It uses Lucas sequences to perform exponentiation in a quadratic field. It is analogous to Pollard's ''p'' − 1 algorithm. ==Algorithm== Choose some integer ''A'' greater than 2 which characterizes the Lucas sequence: : where all operations are performed modulo ''N''. Then any odd prime ''p'' divides whenever ''M'' is a multiple of , where and is the Jacobi symbol. We require that , that is, ''D'' should be a quadratic non-residue modulo ''p''. But as we don't know ''p'' beforehand, more than one value of ''A'' may be required before finding a solution. If , this algorithm degenerates into a slow version of Pollard's p − 1 algorithm. So, for different values of ''M'' we calculate , and when the result is not equal to 1 or to ''N'', we have found a non-trivial factor of ''N''. The values of ''M'' used are successive factorials, and is the ''M''-th value of the sequence characterized by . To find the ''M''-th element ''V'' of the sequence characterized by ''B'', we proceed in a manner similar to left-to-right exponentiation: x=B y=(B^2-2) mod N for each bit of M to the right of the most significant bit if the bit is 1 x=(x *y-B) mod N y=(y^2-2) mod N else y=(x *y-B) mod N x=(x^2-2) mod N V=x 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Williams' p + 1 algorithm」の詳細全文を読む スポンサード リンク
|